The present invention relates to the field of computer graphics and, more particularly, to a method and device for providing high precision texture wrapping.
In modern computer graphics, images or objects are typically modeled by graphics primitives such as points, line segments, polygons, etc. Among the primitives, polygons, particularly triangles, have been commonly used in modeling 2D and 3D images of objects. The underlying reason for this is that polygons such as triangles are generally easier to generate and simpler to support in hardware than other primitives.
The conventional polygon modeling method, however, presents a problem in modeling images or objects having intricate and fine surface details. In particular, modeling such intricate and fine details requires smaller polygons. For example, a large flat wall, which in actuality is a single rectangle, might require thousands of individual bricks to model the intricate and fine details of the surface. Thus, the need to use smaller polygons significantly increases the number polygons that must be used to model an image or object. In computer graphics, processing cost is proportional to the number of polygons used in modeling an image. The reason that the processing cost increases as the number of polygons used increases is that each additional polygon requires more data processing, more data transformation, and more data storage. Hence, modeling of fine and intricate scenes or objects using micro-polygons has been an expensive and impractical process for all but the most expensive graphics systems.
Various alternatives to the micro-polygon modeling method have been devised in modeling images and objects having fine and intricate surface details such as, for example, dense vegetation, walls, etc. One such alternative approach is a method referred to as texture mapping or pattern mapping. In this method an image is applied to a polygon and this polygon with the applied image is drawn as a single polygon. The image is sometimes referred to as a texture or a texture map and its individual elements are sometimes referred to as texels. The texture map typically consists of rectangular arrays of texels, which are associated with data such as color, luminance, color, alpha value, etc. Alternatively, the texture map may be defined by procedural methods.
In texture mapping, a rectangular texture is generally mapped onto the surface of a polygon modeling an object. When mapping a rectangular texture onto a polygon, however, the size of the rectangular texture is often smaller than the size of the polygon. In such cases, a conventional method, which is commonly known as "texture wrapping," is typically used to apply the texture onto the polygon repeatedly until the polygon is entirely covered with the texture.
FIG. 1A illustrates a schematic diagram of an exemplary texture wrapping method. In this example, a rectangular texture 102 of intensity values is defined in a two-dimensional texture coordinate space (s, t) with s and t each ranging from 0 to 1. A polygon 104 has texture coordinates that are twice as large as the texture coordinates of the rectangular texture 102. In this arrangement, rectangular texture 102 is replicated four times onto polygon 104, thereby generating detailed and repeating surface images on the polygon.
When a relatively large number of polygons is used to model a large image or object such as, for example, a field of vegetation or grass, a rectangular texture may be applied thousands of times onto the polygon to generate an image of vegetation with a realistic appearance. Unfortunately in these cases, conventional texture wrapping methods generally do not provide a detailed texture surface due to the lack of precision at the higher texture space coordinates.
For example, FIG. 1B shows a schematic diagram of a conventional texture wrapping method as applied to a triangle 106 having large texture coordinates. Specifically, the triangle 106 is characterized by vertices .alpha., .beta., and .gamma., which have (s, t) texture coordinates of (99998, 1234), (99999, 1234.1), and (99999.17, 1235.769867), respectively. In this texture coordinate arrangement, the texture 102 from the lower texture coordinate may not be applied properly onto the triangle due to a lack of sufficient precision at the higher texture coordinate space. For example, even though the texture coordinates only differ by one or two units, over 20 integer bits may be needed to attain visual accuracy using conventional techniques.
A computer system typically implements texture mapping by assigning a specified number of bits to texture coordinates. For example, texture coordinate variables "s" and "t" may be represented as an 8-bit number. In this configuration, the 8-bit texture coordinate variables do not provide sufficient precision for higher texture coordinates such as (999, 999), to distinguish from neighboring texture coordinates. That is, the 8-bit texture coordinate may distinguish only the first 2.sup.8, i.e., 256, texture coordinate blocks. Thus, the remaining texture coordinates may not be accurately replicated onto the polygon 106, thereby resulting in unrealistic images.
Conventional texture application techniques often employ a well-known barycentric coordinate system based on the areas of sub-triangles within a triangle. For example, a barycentric coordinate system is defined in OpenGL.RTM., version 1.1, available from Silicon Graphics, Inc. FIG. 2 illustrates an exemplary triangle 200 for implementing the barycentric coordinate system. The triangle 200 includes three sides 202, 204, and 206. The triangle 200 is defined by three vertices .alpha., .beta., and .gamma., which have three-dimensional texture coordinates (s.sub..alpha., t.sub..alpha., r.sub..alpha.), (s.sub..beta., t.sub..beta., r.sub..beta.), and (s.sub..gamma., t.sub..gamma., r.sub..gamma.), respectively.
An arbitrary point P within the triangle 200 is characterized by a coordinate (s.sub.P, t.sub.P, r.sub.P). The point P and the vertices .alpha., .beta., and .gamma. define three sides 208, 210, and 212, respectively. The sides 202, 204, and 206 of the triangle 200 and the sides 208, 210, and 212 form three sub-triangles 214, 216, and 218. In this configuration, the coordinate (s.sub.P, t.sub.P, r.sub.P) of the point P is uniquely defined by the areas A, B, and C of sub-triangles 214, 216, and 218, respectively. The areas A, B, and C form the basic coordinate units in the barycentric coordinate system.
To further simplify the barycentric coordinate system, if the area of the triangle 200 is normalized to 1, then the point P can be uniquely defined by the areas of any two sub-triangles. For example, if the areas of sub-triangles 214, 216, and 218 are A, B, and C, respectively, then A+B+C=1. Hence, the area C can be defined in terms of the other two areas: C=1-(A+B). Consequently, the coordinate (s, t, r) of the point P can then be defined by the following barycentric equations based on barycentric coordinates (A, B): EQU s.sub.p =(s.sub..alpha. -s.sub..gamma.)A+(s.sub..beta. -s.sub..gamma.)B+s.sub..gamma. ; Equation 1.1 EQU t.sub.p =(t.sub..alpha. -t.sub..gamma.)A+(t.sub..beta. -t.sub..gamma.)B+t.sub..gamma. ; Equation 1.2
and EQU r.sub.p 32 (r.sub..alpha. -r.sub..gamma.)A+(r.sub..beta. -r.sub..gamma.)B+r.sub..gamma.. Equation 1.3
One drawback of using the conventional barycentric equations in a texture wrapping operation is that they may not provide sufficient precision for large texture coordinates. For example, if s.sub..alpha., s.sub..beta., and s.sub..gamma. are floating point numbers 1005.1, 1010.5, and 1006, respectively, a computer system that implements the barycentric equations may not provide sufficient precision to generate distinct and unique coordinates. In addition, computing s.sub.P, t.sub.P, and r.sub.P using such large floating point numbers requires a substantial number of subtraction operations, which require a significant number of subtractors to implement in hardware.
Thus, what is needed is a method and a device for efficiently performing texture wrapping with high precision even for large texture coordinates without requiring costly hardware.